Bao lồi
Bao lồi

Bao lồi

Trong hình học, bao lồi của một hình là tập hợp lồi nhỏ nhất chứa hình đó. Bao lồi có thể được định nghĩa là giao của tất cả tập lồi chứa một tập con cho trước của một không gian Euclid, hoặc là tập hợp gồm tất cả tổ hợp lồi của các điểm trong tập con đó. Đối với một tập con bị chặn của mặt phẳng, bao lồi có thể được minh họa thành một hình được bao bởi một sợi dây đàn hồi kéo dãn xung quanh tập con đó.Bao lồi của tập mở là bao lồi mở, và bao lồi của tập compact là bao lồi compact. Mỗi tập lồi compact đều là bao lồi của các điểm cực biên của nó. Toán tử bao lồi là một ví dụ về toán tử đóng, và một antimatroid có thể được biểu diễn bằng cách áp dụng toán tử đóng này cho tập hợp hữu hạn các điểm. Các bài toán thuật toán về việc tìm bao lồi của một tập hợp hữu hạn các điểm trong mặt phẳng hoặc các không gian Euclid ít chiều khác và bài toán đối ngẫu về các nửa không gian giao nhau đều là những vấn đề cơ bản của hình học tính toán. Chúng có thể được giải trong thời gian O ( n log ⁡ n ) {\displaystyle O(n\log n)} đối với tập hợp điểm hai chiều hoặc ba chiều, và trong thời gian bằng với độ phức tạp thời gian trong trường hợp tệ nhất được cho bởi định lý cận trên ở không gian nhiều chiều hơn.Cùng với tập hợp điểm hữu hạn, bao lồi cũng đã được nghiên cứu đối với đa giác đơn, chuyển động Brown, đường cong ghềnhđồ thị trên của hàm. Bao lồi được ứng dụng rộng rãi trong toán học, thống kê, tối ưu hóa tổ hợp, kinh tế, mô hình hóa hình học và tập tính học. Một số cấu trúc liên quan đến nó bao gồm bao lồi trực giao, lớp lồi, chỏm lồi, tam giác đạc Delaunaysơ đồ Voronoi.

Tài liệu tham khảo

WikiPedia: Bao lồi http://mathworld.wolfram.com/ConvexHull.html http://www.heldermann-verlag.de/jgg/jgg01_05/jgg01... http://citeseerx.ist.psu.edu/viewdoc/download?doi=... //www.ams.org/mathscinet-getitem?mr=0237460 //www.ams.org/mathscinet-getitem?mr=0274683 //www.ams.org/mathscinet-getitem?mr=0356305 //www.ams.org/mathscinet-getitem?mr=0404097 //www.ams.org/mathscinet-getitem?mr=1173256 //www.ams.org/mathscinet-getitem?mr=1216521 //www.ams.org/mathscinet-getitem?mr=1226891